package 栈队列与哈希表;

import java.util.HashMap;

/**
 * 给定一个数组，找出数组中是否有两个数对（a, b）和（c, d），
 * 使得a+b=c+d，其中a、b、c和d是不同的元素。如果有多个答案，打印任意一个即可。
 * 例如，给定数组：{3, 4, 7, 10, 20, 9, 8}，
 * 可以找到两个数对（3, 8）和（4, 7），使得3+8=4+7
 */
public class I如何从数组中找出满足aPlusbEqcPlusd的两个数对 {

    /**
     * 分析与解答
     * 最简单的方法就是使用四重遍历，对所有可能的数对，判断是否满足题目要求，
     * 如果满足则打印出来，但是这种方法的时间复杂度为O（N^4），很显然不满足要求。
     * 下面介绍另外一种方法——Hash法，算法的主要思路：以数对为单位进行遍历，
     * 在遍历过程中，把数对和数对的值存储在哈希表中（键为数对的和，值为数对）。
     * 当遍历到一个键值对，如果它的和在哈希表中已经存在，那么就找到了满足条件的键值对。
     * 下面使用HashMap为例，实现代码如下
     */
    private class Pair {
        int first, second;

        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    boolean findPairs(int arr[]) {
        //键为数对的和，值为数对
        HashMap<Integer, Pair> sumPair = new HashMap<Integer, Pair>();
        int n = arr.length;
        //遍历数组中所有可能的数对
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; ++j) {
                int sum = arr[i] + arr[j];
                //如果这个数对的和在map中没有，则放入map中
                if (!sumPair.containsKey(sum)) {
                    sumPair.put(sum, new Pair(i, j));
                    //map中已经存在与sum相同的数对了，找出来并打印
                } else {
                    //找出已经遍历过的并存储在map中和为sum的数对
                    Pair p = sumPair.get(sum);
                    System.out.println("(" + arr[p.first]
                            + "," + arr[p.second] + "),(" +
                            arr[i] + "," + arr[j] + ")");
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int arr[] = {3, 4, 7, 10, 20, 9, 8};
        I如何从数组中找出满足aPlusbEqcPlusd的两个数对 a =
                new I如何从数组中找出满足aPlusbEqcPlusd的两个数对();
        a.findPairs(arr);
    }
}
